import DoublyNode from "./DoublyNode.js";
import LinkedList from "./LinkedList.js";

/**
 * 双向链表
 */
export default class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
  }

  /**
   * 将元素插入到链表的指定位置，如果失败则返回null
   * @param {*} value 需要插入的项
   * @param {number} index 需要插入的位置
   * @returns {DoublyLinkedList|null}
   */
  insert(value, index) {
    if (index < 0 || index > this.count) {
      return null;
    }

    const newNode = new DoublyNode(value);

    if (index === 0) {
      if (!this.head) {
        // 如果不存在头节点，则令head和tail都为新节点
        this.head = newNode;
        this.tail = newNode;
      } else {
        // 如果存在头节点，则将新节点添加到头节点前面
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      }
    } else if (index === this.count) {
      // 添加到链表最后
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else {
      const prevNode = this.findAt(index - 1);
      newNode.next = prevNode.next;
      newNode.prev = prevNode;
      prevNode.next.prev = newNode;
      prevNode.next = newNode;
    }

    this.count++;
    return this;
  }

  /**
   * 从链表中移除节点
   * @param {*} value 需要移除的节点
   * @returns {DoublyNode|null}
   */
  remove(value) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    // 遍历链表
    while (currentNode) {
      if (value === currentNode.value) {
        if (currentNode === this.head) {
          // 当前节点为head时
          // 将head设置为被删除节点的下一个节点
          this.head = currentNode.next;

          // 如果head不为null
          if (this.head) {
            this.head.prev = null;
          }

          // 此时链表只有一个节点，即head，tail都为同一个节点
          if (currentNode === this.tail) {
            this.tail = null;
          }
        } else if (currentNode === this.tail) {
          // 当前节点与tail节点相同
          this.tail = currentNode.prev;
          this.tail.next = null;
        } else {
          currentNode.prev.next = currentNode.next;
          currentNode.next.prev = currentNode.prev;
        }

        this.count--;
        return currentNode;
      }

      currentNode = currentNode.next;
    }

    return currentNode;
  }

  /**
   * 按指定位置删除元素
   * @param {number} index 需要删除元素的位置
   * @returns {DoublyNode|null}
   */
  removeAt(index) {
    if (index < 0 || index >= this.count) {
      return null;
    }

    let removeNode = null;

    if (index === 0) {
      removeNode = this.head;
      this.head = this.head.next;

      if (this.count === 1) {
        // 如果只有一个元素，则tail节点也需要设置null
        this.tail = null;
      } else {
        // 将新的head节点的prev设置为null
        this.head.prev = null;
      }
    } else if (index === this.count - 1) {
      // 删除tail节点
      removeNode = this.tail;
      this.tail = this.tail.prev;
      this.tail.next = null;
    } else {
      removeNode = this.findAt(index);
      removeNode.prev.next = removeNode.next;
      removeNode.next.prev = removeNode.prev;
    }

    this.count--;
    return removeNode;
  }
}
